/*
 ============================================================================
 Name        : msplicedag.c
 Author      : Kishi & Ronaldo
 Description : Genetic Algorithm for the Multiple Spliced Alignment Problem
 ============================================================================
 */


/*
 * Pendencias:
 *
 * 1 - colocar flag para permitir soluções vazias
 * 2 - possibilitar o ponto de corte na sequencia 2 na hora de fazer o cruzamento
 *
 * */

/*
Passo 1: gere uma população  inicial de forma aleatória;
Passo 2: calcule o fitness de cada indivíduo e ordene-os (de forma não-decrescente) pelo valor calculado;
Passo 3: enquanto o critério de parada não for atingido (número de gerações, fitness acima de um threshold, etc.)
Passo 3.1: selecione alguns indivíduos (que irão sofrer mutações e se cruzar) por meio de uma roleta. Essa
 seleção está dividida em dois passos. No primeiro passo, para cada indivíduo i da população corrente,
  você deve calcular a probabilidade (p(i)) dele ser um bom indivíduo ou não. Para isso, divida o
  fitness de i pela soma dos fitnesses de todos os indivíduos. No segundo passo, para cada indivíduo
   i da população corrente, você deve gerar um número (n(i)) aleatório (de duas casas decimais) entre
    0 e 1. Se o n(i) > p(i), então selecione esse indivíduo. A intenção com essa forma de seleção
     é não deixar de fora pais ruins que poderiam, porventura, da origem a filhos bons. Afinal,
      quantas crianças bonitas nós conhecemos cujos pais são feios de dar dó? :):)
Passo 3.2: realize os cruzamentos entre os indivíduos selecionados no passo 3.1 (i com i+1, i+1 com i+2, ...) ;
Passo 3.3:  gere mutações em alguns indivíduos selecionados no passo 3.1. Escolha os indivíduos da
seguinte forma: para cada indivíduo i, gere um número aleatório (de duas casas decimais) entre 0 e
1 - n(i). Se o n(i) >= 0,99, então escolha esse indivíduo e insira algumas mutações nele. Observe
 que, dessa forma, os indivíduos possuem apenas 1% de chance de ser escolhido para sofrer mutação.
Passo 3.4: calcule o fitness de cada indivíduo gerado nos passos 3.2 e 3.3 e ordene-os (de forma
 não-decrescente) pelo valor calculado;
Passo 3.5: pegue os melhores indivíduos dos três conjuntos gerados: aquele gerado ao final do
passo 3.1, ao final do  passo  3.2 e ao final do passo 3.3
Passo 3.6: volte ao Passo 3.
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>    /*time()*/
#include "iolib.h"
#include "alglib.h"

#define POPULATION_SIZE 20
#define GENERATION_SIZE 10
#define TENTATIVAS_SIZE 10

#define DELETION 5
/*Esse aqui dá 10% de chance de realizar a inserção esperta e 40% de chance de realizar a inserção aleatória*/
/*#define SMART_INSERTION 6*/
/*Esse aqui dá 50% de chance de realizar a inserção esperta*/
#define SMART_INSERTION 10
#define SMART_DELETION 3


char *get_sequence(char *g, int **b, struct block *blocks, int conc_size);
int get_score(char **t, int tsize, int *tsizes, char *g, int gsize);
void zera_blocos_usados(char *b, int bsize);
void marca_blocos_usados(struct block *pop, char* blocos_usados, int bsize);
int try_to_insert(int bsize, char *blocos_usados, struct block **population, struct block **blocos_sobrepostos, int i, int **b, int *tamanho_concat);
void calcula_scores(char *g, char **t, int tsize, int *tsizes, int **b, struct block **population, int popsize, int *tamanho_concat, int *score);
int calcula_um_score(char *g, char **t, int tsize, int *tsizes, int **b, struct block **population, int *tamanho_concat, int i);
void copy_solution(struct block *b, struct block **individuo);
struct block *join(struct block *b1, struct block *b2, int index, int **b, int *tam, int *qtd, int tam_qtd_index);
int simulated_insertion_score(char *g, char **t, int tsize, int *tsizes, struct block **population, int i, int **b, int *tamanho_concat, int blococandidato);
int simulated_deletion_score(char *g, char **t, int tsize, int *tsizes, struct block **population, int i, int **b, int *tamanho_concat, int blocoremovido);


int main(int argc, char *argv[])
{
	char *g; /*Sequência G*/
	char **tfilenames; /*Nomes dos arquivos das sequências do conj T*/
	char **t; /*Conjunto T*/

	/*Tamanhos de g e T */
	int gsize;
	int tsize;

	int *tsizes; /*Tamanho de cada sequência em T*/
	int maior_t; /*Armazena o valor da maior sequência de T*/

	/*Blocos*/
	int **b;
	int bsize;


	/*População principal*/
	struct block **population; /*População*/
	char *blocos_usados; /* Marca quais blocos estão na solução */
	int *qtd_de_blocos; /*Quantidade de blocos utilizados em cada indivíduo, gerada randomicamente*/
	int *tamanho_concat; /* Armazena o tamanho da concatenação dos blocos de cada indivíduo */
	int *score; /* Armazena o score de cada indivíduo */
	float *p; /*Probabilidade de um indivíduo ser bom*/
	/*int score_total;*/ /*Total dos scores usado para calcular p(i)*/
	float n; /*Número aleatório entre 0 e 1 para ser comparado com cada p(i)*/

	/*População escolhida como pais para os cruzamentos*/
	struct block **population_chosen_parents; /*População*/
	int *qtd_de_blocos_chosen_parents; /*Quantidade de blocos utilizados em cada indivíduo, gerada randomicamente*/
	int *tamanho_concat_chosen_parents; /* Armazena o tamanho da concatenação dos blocos de cada indivíduo */
	int *score_chosen_parents; /* Armazena o score de cada indivíduo */
	int population_chosen_parents_size; /*Quantidade de pais escolhidos para os cruzamentos*/

	/*População gerada pelos cruzamentos*/
	struct block **population_from_crossover; /*População*/
	int *qtd_de_blocos_from_crossover; /*Quantidade de blocos utilizados em cada indivíduo, gerada randomicamente*/
	int *tamanho_concat_from_crossover; /* Armazena o tamanho da concatenação dos blocos de cada indivíduo */
	int *score_from_crossover; /* Armazena o score de cada indivíduo */
	int population_from_crossover_size; /*Quantidade de pais escolhidos para os cruzamentos*/

	/*População gerada pelas mutações*/
	struct block **population_from_mutation; /*População*/
	int *qtd_de_blocos_from_mutation; /*Quantidade de blocos utilizados em cada indivíduo, gerada randomicamente*/
	int *tamanho_concat_from_mutation; /* Armazena o tamanho da concatenação dos blocos de cada indivíduo */
	int *score_from_mutation; /* Armazena o score de cada indivíduo */
	int population_from_mutation_size; /*Quantidade de pais escolhidos para os cruzamentos*/

	struct block **blocos_sobrepostos; /* Marca quais blocos são incompatíveis */

	struct block *aux;

	/*Índices genéricos*/
	int i,j, k, gen_index;

	/* Flag para laço de criação de indivíduos */
	char continua;

	/*Bloco escolhido randomicamente*/
	int rand_block = 1; /*rom_crossover Inicializa p/ evitar warning */

	/* Tipo da modificação */
	char mutation_type;

	/*Quantidade de blocos a ser modificado*/
	int mutation_len;

	/* Número do bloco a ser modificado */
	int mutation_index;

	/* Posição da primeira sequência de onde começará o cruzamento */
	int crossover_center;

	/* Fitness mínimo de cada população*/
	int score_min;

	/* Melhor fitness dos blocos candidatos à mutação*/
	int bestscore;
	int bestblock;
	int simulatedscore;

	FILE *out1;
	FILE *out2;
	FILE *out3;
	FILE *out4;
	FILE *out5;
	char out1_name[100];
	char out2_name[100];
	char out3_name[100];
	char out4_name[100];
	char out5_name[100];

	strcpy(out1_name, argv[4]);
	strcat(out1_name, ".out1");

	strcpy(out2_name, argv[4]);
	strcat(out2_name, ".out2");

	strcpy(out3_name, argv[4]);
	strcat(out3_name, ".out3");

	strcpy(out4_name, argv[4]);
	strcat(out4_name, ".out4");

	strcpy(out5_name, argv[4]);
	strcat(out5_name, ".out5");

	out1 = openFileForWriting(out1_name);
	out2 = openFileForWriting(out2_name);
	out3 = openFileForWriting(out3_name);
	out4 = openFileForWriting(out4_name);
	out5 = openFileForWriting(out5_name);


	fprintf(out2, "Arquivo com as P1's (populações básicas)\n");
	fprintf(out3, "Arquivo com as P2's (populações de pais escolhidos)\n");
	fprintf(out4, "Arquivo com as P3's (populações provenientes dos cruzamentos)\n");
	fprintf(out5, "Arquivo com as P4's (populações resultantes das mutações)\n");


	fprintf(out2, "INSTANCE %s\n", argv[4]);
	fprintf(out3, "INSTANCE %s\n", argv[4]);
	fprintf(out4, "INSTANCE %s\n", argv[4]);
	fprintf(out5, "INSTANCE %s\n", argv[4]);



	/*Lê g*/
	g = readFastaSequence(argv[1], &gsize);

	/*Lê os blocos de g e preenche sua quantidade (bsize)*/
	b = readBlocks(argv[2], &bsize);

	/* Constrói o grafo de sobreposição de blocos */
	blocos_sobrepostos = (struct block **) malloc(sizeof(struct block *) * bsize);
	for(i = 0; i < bsize; i++)
		blocos_sobrepostos[i] = NULL;
	for(i = 1; i < bsize; i++)
	{
		/*Verifica os blocos antes de i*/
		j = i - 1;
		while( j > 0 )
		{
			if(b[0][i] <= b[1][j])
				insert_block(&(blocos_sobrepostos[i]), j);
			j--;
		}

		/*Verifica os blocos depoi*s de i*/
		j = i + 1;
		while( j < bsize && b[1][i] >= b[0][j])
		{
			insert_block(&(blocos_sobrepostos[i]), j);
			j++;
		}
	}

	/*Lê os nomes dos arquivos de T*/
	tfilenames = readcDNAFilenames(argv[3], &tsize);

	/*Aloca os vetores t e o com os tamanhos das sequências de T*/
	tsizes = (int *) malloc(sizeof(int) * tsize);
	t = (char **) malloc(sizeof(char*) * tsize);

	/*Lê cada uma das sequências de T*/
	maior_t = -1;
	for(i = 0; i < tsize; i++)
	{
		t[i] = readFastaSequence(tfilenames[i], &(tsizes[i]) );
		if(tsizes[i] > maior_t)
			maior_t = tsizes[i];
	}

	/*Inicializa a semente randômica */
	srand(time(0));

	/*Inicializações de vetores da população principal*/
	blocos_usados = (char *) malloc(sizeof(char) * bsize);
	qtd_de_blocos = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	tamanho_concat = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	population = (struct block **)malloc(sizeof(struct block *) * POPULATION_SIZE);
	score = (int *)malloc(sizeof(int) * POPULATION_SIZE);
	p = (float *)malloc(sizeof(float) * POPULATION_SIZE);

	/*Inicializações dos vetores das populações adicionais*/
	population_chosen_parents = (struct block **)malloc(sizeof(struct block *) * POPULATION_SIZE);
	qtd_de_blocos_chosen_parents = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	tamanho_concat_chosen_parents = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	score_chosen_parents = (int *)malloc(sizeof(int) * POPULATION_SIZE);

	population_from_crossover = (struct block **)malloc(sizeof(struct block *) * POPULATION_SIZE);
	qtd_de_blocos_from_crossover = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	tamanho_concat_from_crossover = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	score_from_crossover = (int *)malloc(sizeof(int) * POPULATION_SIZE);

	population_from_mutation = (struct block **)malloc(sizeof(struct block *) * POPULATION_SIZE);
	qtd_de_blocos_from_mutation = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	tamanho_concat_from_mutation = (int *) malloc(sizeof(int) * POPULATION_SIZE);
	score_from_mutation = (int *)malloc(sizeof(int) * POPULATION_SIZE);


	/* Gera população inicial */
	/*==========================================================================================================*/
	/*==========================================================================================================*/
	i = 0;
	while(i < POPULATION_SIZE)
	{
		/*Inicializa o vetor de blocos utilizados, para saber que já foi inserido no indivíduo atual ou não*/
		zera_blocos_usados(blocos_usados, bsize);

		/*Inicializa o indivíduo*/
		population[i] = NULL;
		tamanho_concat[i] = 0;

		population_chosen_parents[i] = NULL;
		tamanho_concat_chosen_parents[i] = 0;

		population_from_crossover[i] = NULL;
		tamanho_concat_from_crossover[i] = 0;

		population_from_mutation[i] = NULL;
		tamanho_concat_from_mutation[i] = 0;


		do
		{
			qtd_de_blocos[i] = rand() % bsize;
		}while(qtd_de_blocos[i] == 0);

		j = 0;
		continua = YES;
		while(continua == YES && j < qtd_de_blocos[i] && tamanho_concat[i] < maior_t)
		{
			rand_block = try_to_insert(bsize, blocos_usados, population, blocos_sobrepostos, i, b, tamanho_concat);

			if(rand_block != -1)
			{
				blocos_usados[rand_block] = YES;
				j++;
			}
			else
			{
				free_blocks(&population[i]);
				continua = NO;
			}
		}
		if(rand_block != -1)
		{
			qtd_de_blocos[i] = j;  /*caso ele saia pq a concatenação ultrapassou o tamanho da maior sequência de T, atualiza a qtd de blocos*/
			tamanho_concat[i]++; /* Incrementa para manter o padrão de inutilizar a posição 0 */
			i++;
		}
	}

	/* FIM Gera população inicial */
	/*==========================================================================================================*/
	/*==========================================================================================================*/

	/*Calcula os scores de cada indivíduo*/

	calcula_scores(g, t, tsize, tsizes, b, population,POPULATION_SIZE, tamanho_concat, score);

	/*Ordena população*/
	sort_blocks(population, score, POPULATION_SIZE, tamanho_concat, qtd_de_blocos);

	/*QUANTIDADE DE EVOLUÇÕES*/
	for(gen_index = 0; gen_index < GENERATION_SIZE; gen_index++)
	{
		/*Imprime todas as gerações*/
		sort_blocks(population, score, POPULATION_SIZE, tamanho_concat, qtd_de_blocos);
		fprintf(out2, "População %d\n", gen_index + 1);
		print_blocks_with_info_to_file(population, POPULATION_SIZE, score, tamanho_concat, qtd_de_blocos, b, out2);

		/*//TODO Descomentar se voltar pra idéia do Said*/
		/*score_total = 0;
		for(i = 0; i < POPULATION_SIZE; i++)
			score_total += score[i];*/

		/*//TODO remover se voltar pra idéia do Said*/
		score_min = score[0];
		for(i = 1; i < POPULATION_SIZE; i++)
		{
			if(score[i] < score_min)
				score_min = score[i];
		}

		/*Escolhendo os pais*/
		population_chosen_parents_size = 0;
		for(i = 0; i < POPULATION_SIZE; i++)
		{
			/*//TODO Código com a idéia do Said*/
/*			p[i] = 1 - (float)score[i]/(float)score_total;
			n = ((float)(rand() % 101)) / 100;
			if(n <= p[i])
			{
				copy_solution(population[i],&(population_chosen_parents[population_chosen_parents_size]));
				qtd_de_blocos_chosen_parents[population_chosen_parents_size] = qtd_de_blocos[i];
				tamanho_concat_chosen_parents[population_chosen_parents_size] = tamanho_concat[i];
				score_chosen_parents[population_chosen_parents_size] = score[i];
				population_chosen_parents_size++;
			}*/
			/*//TODO Código com a idéia do Kishi e do Ronaldo (remover o score_min se não for utilizar esse código)*/
			p[i] = 1 - (float)score[i]/(float)score_min;
			n = ((float)(rand() % 101)) / 100;
			if(n <= p[i])
			{
				copy_solution(population[i],&(population_chosen_parents[population_chosen_parents_size]));
				qtd_de_blocos_chosen_parents[population_chosen_parents_size] = qtd_de_blocos[i];
				tamanho_concat_chosen_parents[population_chosen_parents_size] = tamanho_concat[i];
				score_chosen_parents[population_chosen_parents_size] = score[i];
				population_chosen_parents_size++;
			}
		}
		/*Verifica se ele escolheu o mínimo de indivíduos necessários, se não, pega o mínimo necessário*/
		i = 0;
		while(population_chosen_parents_size < (POPULATION_SIZE - ((POPULATION_SIZE / 3) * 2)) )
		{
			copy_solution(population[i],&(population_chosen_parents[population_chosen_parents_size]));
			qtd_de_blocos_chosen_parents[population_chosen_parents_size] = qtd_de_blocos[i];
			tamanho_concat_chosen_parents[population_chosen_parents_size] = tamanho_concat[i];
			score_chosen_parents[population_chosen_parents_size] = score[i];
			population_chosen_parents_size++;
			i++;
		}

		/*Realizando os cruzamentos entre os pais escolhidos*/
		population_from_crossover_size = 0;
		for(i = 0; i < (population_chosen_parents_size - 1); i++)
		{
			if(qtd_de_blocos_chosen_parents[i] > 2)
				crossover_center = (rand() % (qtd_de_blocos_chosen_parents[i] - 2)) + 1; /* Escolhe entre os blocos de j, sem a possibilidade de escolher no primeiro ou no último */
			else
				crossover_center = 0;

			/*//TODO Código para tornar a escolha de pais aleatória*/
			population_from_crossover[population_from_crossover_size] = join(population_chosen_parents[i], population_chosen_parents[rand() % population_chosen_parents_size],
								crossover_center, b, tamanho_concat_from_crossover, qtd_de_blocos_from_crossover, population_from_crossover_size);

			/*//TODO Cruza i com i + 1*/
			/*population_from_crossover[population_from_crossover_size] = join(population_chosen_parents[i], population_chosen_parents[i + 1],
					crossover_center, b, tamanho_concat_from_crossover, qtd_de_blocos_from_crossover, population_from_crossover_size);*/
			population_from_crossover_size++;
		}

		/*Realizando mutações em alguns indivíduos*/

		/*primeiro copia a população proveniente do cruzamento para a nova população que será mutada*/
		for(i = 0; i < population_from_crossover_size; i++)
		{
			copy_solution(population_from_crossover[i], &(population_from_mutation[i]));
			qtd_de_blocos_from_mutation[i] = qtd_de_blocos_from_crossover[i];
			tamanho_concat_from_mutation[i] = tamanho_concat_from_crossover[i];
			score_from_mutation[i] = score_from_crossover[i];

		}
		population_from_mutation_size = population_from_crossover_size;

		/*Aqui começa o código para realizar as mutações*/
		for(i = 0; i < population_from_mutation_size; i++)
		{
			/*//TODO Sempre realiza mutações.*/
			/*n = ((float)(rand() % 101)) / 100;
			if(n < 0.2)*/
			{
				mutation_len = (rand() % qtd_de_blocos_from_mutation[i]) + 1;

				for(j = 0; j < mutation_len; j++)
				{
					mutation_type = rand() % 10;
					/*Tem 50% de chances de realizar uma remoção de base*/
					if(mutation_type < DELETION)
					{
						if(mutation_type < SMART_DELETION && (qtd_de_blocos_from_mutation[i] > 1) )
						{
							/*Calcula o score na hora pois ele pode estar desatualizado graças a uma deleção ou inserção idiota anterior*/
							bestscore = score_from_mutation[i] = calcula_um_score(g, t, tsize, tsizes, b, population_from_mutation, tamanho_concat_from_mutation, i);
							bestblock = -1;
							/*Escolhendo o bloco que ao ser removido, mais melhora (sic) a solução*/
							aux = population_from_mutation[i];
							while(aux != NULL)
							{
								simulatedscore = simulated_deletion_score(g, t, tsize, tsizes, population_from_mutation, i, b, tamanho_concat_from_mutation, aux->block);
								if(simulatedscore > bestscore)
								{
									bestscore = simulatedscore;
									bestblock = aux->block;
								}
								aux = aux->next;
							}
							if( bestblock != -1 )
							{
								/*Removendo de fato o novo bloco que melhora a solução e atualizando os vetores necessários*/
								delete_block_by_content(&(population_from_mutation[i]), bestblock);
								qtd_de_blocos_from_mutation[i]--;
								tamanho_concat_from_mutation[i] = tamanho_concat_from_mutation[i] - (b[1][bestblock] - b[0][bestblock] + 1);
								score_from_mutation[i] = bestscore;
							}
						}
						else
						{
							mutation_index = rand() % qtd_de_blocos_from_mutation[i];
							if(qtd_de_blocos_from_mutation[i] > 1)
							{
								int deleted_block;
								deleted_block = delete_block(&(population_from_mutation[i]), mutation_index);
								qtd_de_blocos_from_mutation[i]--;
								tamanho_concat_from_mutation[i] = tamanho_concat_from_mutation[i] - ((b[1][deleted_block] - b[0][deleted_block]) + 1);
							}
						}
					}
					/*Os outros 50% de chance serão divididos em 10% para inserção inteligente e 40% para inserção idiota*/
					else
					{
						/*10% de chance para inserção inteligente*/
						if(mutation_type < SMART_INSERTION)
						{
							/*Buscaremos o melhor indivíduo para inserir ao invés de escolher um aleatório*/
							marca_blocos_usados(population_from_mutation[i], blocos_usados, bsize);
							/*Calcula o score na hora pois ele pode estar desatualizado graças a uma deleção ou inserção idiota anterior*/
							bestscore = score_from_mutation[i] = calcula_um_score(g, t, tsize, tsizes, b, population_from_mutation, tamanho_concat_from_mutation, i);
							bestblock = -1;
							/*Escolhendo o bloco que mais melhora (sic) a solução*/
							for(k = 0; k < bsize; k++)
							{
								if(blocos_usados[k] == NO && overlap(population_from_mutation[i], blocos_sobrepostos, k) == NO)
								{
									simulatedscore = simulated_insertion_score(g, t, tsize, tsizes, population_from_mutation, i, b, tamanho_concat_from_mutation, k);
									if(simulatedscore > bestscore)
									{
										bestscore = simulatedscore;
										bestblock = k;
									}
								}
							}
							if( bestblock != -1 )
							{
								/*Inserindo de fato o novo bloco que melhora a solução e atualizando os vetores necessários*/
								insert_block(&(population_from_mutation[i]), bestblock);
								qtd_de_blocos_from_mutation[i]++;
								tamanho_concat_from_mutation[i] += b[1][bestblock] - b[0][bestblock] + 1;
								score_from_mutation[i] = bestscore;
							}
						}
						/*Os 40% restantes de chance para inserção aleatória*/
						else
						{
							marca_blocos_usados(population_from_mutation[i], blocos_usados, bsize);
							rand_block = try_to_insert(bsize, blocos_usados, population_from_mutation, blocos_sobrepostos, i, b, tamanho_concat_from_mutation);
							if(rand_block != -1)
							{
								qtd_de_blocos_from_mutation[i]++;
							}
						}
					}
				}
			}
		}

		/*Ordenando as novas populações*/
		/*Essa primeira não precisa calcular o score pq já veio calculado*/
		sort_blocks(population_chosen_parents, score_chosen_parents, population_chosen_parents_size, tamanho_concat_chosen_parents, qtd_de_blocos_chosen_parents);
		fprintf(out3, "População %d\n", gen_index + 1);
		print_blocks_with_info_to_file(population_chosen_parents, population_chosen_parents_size, score_chosen_parents, tamanho_concat_chosen_parents, qtd_de_blocos_chosen_parents, b, out3);

		calcula_scores(g, t, tsize, tsizes, b, population_from_crossover, population_from_crossover_size, tamanho_concat_from_crossover, score_from_crossover);
		sort_blocks(population_from_crossover, score_from_crossover, population_from_crossover_size, tamanho_concat_from_crossover, qtd_de_blocos_from_crossover);
		fprintf(out4, "População %d\n", gen_index + 1);
		print_blocks_with_info_to_file(population_from_crossover, population_from_crossover_size, score_from_crossover, tamanho_concat_from_crossover, qtd_de_blocos_from_crossover, b, out4);

		calcula_scores(g, t, tsize, tsizes, b, population_from_mutation, population_from_mutation_size, tamanho_concat_from_mutation, score_from_mutation);
		sort_blocks(population_from_mutation, score_from_mutation, population_from_mutation_size, tamanho_concat_from_mutation, qtd_de_blocos_from_mutation);
		fprintf(out5, "População %d\n", gen_index + 1);
		print_blocks_with_info_to_file(population_from_mutation, population_from_mutation_size, score_from_mutation, tamanho_concat_from_mutation, qtd_de_blocos_from_mutation, b, out5);

/*		printf("População inicial\n");
		print_blocks_with_info(population, POPULATION_SIZE, score, tamanho_concat, qtd_de_blocos);
		printf("População escolhida\n");
		print_blocks_with_info(population_chosen_parents, population_chosen_parents_size, score_chosen_parents, tamanho_concat_chosen_parents, qtd_de_blocos_chosen_parents);
		printf("População cruzada\n");
		print_blocks_with_info(population_from_crossover, population_from_crossover_size, score_from_crossover, tamanho_concat_from_crossover, qtd_de_blocos_from_crossover);
		printf("População mutada\n");
		print_blocks_with_info(population_from_mutation, population_from_mutation_size, score_from_mutation, tamanho_concat_from_mutation, qtd_de_blocos_from_mutation);*/

		/*printf("Population: %d\n", POPULATION_SIZE);
		printf("Population 10%c: %d\n", '%',(POPULATION_SIZE/10));
		printf("Population from crossover and from mutation: %d\n", ((POPULATION_SIZE - (POPULATION_SIZE/10)) / 3) * 2);
		printf("Population chosen parents: %d\n", (POPULATION_SIZE - (POPULATION_SIZE/10) - (((POPULATION_SIZE - (POPULATION_SIZE/10)) / 3) * 2)));*/

		/*Escolhendo os melhores das três populações*/
		for(i = (POPULATION_SIZE/10); i < POPULATION_SIZE; i++)
		{
			free_blocks(&(population[i]));
		}

		j = (POPULATION_SIZE/10);
		for(i = 0; i < ((POPULATION_SIZE - (POPULATION_SIZE/10)) / 3); i++)
		{
			copy_solution(population_from_crossover[i], &(population[j]));
			qtd_de_blocos[j] = qtd_de_blocos_from_crossover[i];
			tamanho_concat[j] = tamanho_concat_from_crossover[i];
			score[j] = score_from_crossover[i];


			copy_solution(population_from_mutation[i], &(population[j + 1]));
			qtd_de_blocos[j+1] = qtd_de_blocos_from_mutation[i];
			tamanho_concat[j+1] = tamanho_concat_from_mutation[i];
			score[j+1] = score_from_mutation[i];

			j+=2;
		}
		for(i = 0; i < (POPULATION_SIZE - (POPULATION_SIZE/10) - (((POPULATION_SIZE - (POPULATION_SIZE/10)) / 3) * 2)); i++)
		{
			copy_solution(population_chosen_parents[i], &(population[j]));
			qtd_de_blocos[j] = qtd_de_blocos_chosen_parents[i];
			tamanho_concat[j] = tamanho_concat_chosen_parents[i];
			score[j] = score_chosen_parents[i];

			j++;
		}

		/*Limpando as populações auxiliares*/
		for(i = 0; i < population_chosen_parents_size; i++)
		{
			free_blocks(&(population_chosen_parents[i]));
		}
		for(i = 0; i < population_from_crossover_size; i++)
		{
			free_blocks(&(population_from_crossover[i]));
		}
		for(i = 0; i < population_from_mutation_size; i++)
		{
			free_blocks(&(population_from_mutation[i]));
		}
	}

	/*Calcula os scores de cada indivíduo*/
	calcula_scores(g, t, tsize, tsizes, b, population,POPULATION_SIZE, tamanho_concat, score);
	/*Ordena população*/
	sort_blocks(population, score, POPULATION_SIZE, tamanho_concat, qtd_de_blocos);

	/*Imprime a última geração*/
	sort_blocks(population, score, POPULATION_SIZE, tamanho_concat, qtd_de_blocos);
	fprintf(out2, "Última População %d\n", gen_index + 1);
	print_blocks_with_info_to_file(population, POPULATION_SIZE, score, tamanho_concat, qtd_de_blocos, b, out2);

	aux = population[0];

	while(aux)
	{
		fprintf(out1, "%d..%d,", b[0][aux->block], b[1][aux->block]);
		aux = aux->next;
	}

	fclose(out1);
	fclose(out2);
	fclose(out3);
	fclose(out4);
	fclose(out5);


	free(qtd_de_blocos);
	free(blocos_usados);
	free(tamanho_concat);
	free(score);
	free(p);

	free_all_blocks(&blocos_sobrepostos, bsize);

	/*Liberando a matriz de populações*/
	free_all_blocks(&population, POPULATION_SIZE);
	/*free(population);*/

	/*Liberando as informações das populações adicionais*/
	free_all_blocks(&population_chosen_parents, population_chosen_parents_size);
	free(qtd_de_blocos_chosen_parents);
	free(tamanho_concat_chosen_parents);
	free(score_chosen_parents);

	free_all_blocks(&population_from_crossover, population_from_crossover_size);
	free(qtd_de_blocos_from_crossover);
	free(tamanho_concat_from_crossover);
	free(score_from_crossover);

	free_all_blocks(&population_from_mutation, population_from_mutation_size);
	free(qtd_de_blocos_from_mutation);
	free(tamanho_concat_from_mutation);
	free(score_from_mutation);


	free(g);
	/*Libera a matriz com nomes dos arquivos*/
	for(i = 0; i < tsize; i++)
		free(tfilenames[i]);
	free(tfilenames);

	/*Libera a matriz com as sequências de T*/
	for(i = 0; i < tsize; i++)
		free(t[i]);
	free(t);
	free(tsizes);

	/*Libera memória dos blocos*/
	free(b[0]);
	free(b[1]);
	free(b[2]);
	free(b);

	return EXIT_SUCCESS;
}




char *get_sequence(char *g, int **b, struct block *blocks, int conc_size)
{
	char *new;
	int i;
	struct block *aux = blocks;
	int newi;
	int block_size;

	new = (char *)malloc(sizeof(char) * conc_size);
	new[0] = ' '; /*Coloca lixo na primeira posição para manter padrão*/
	newi = 1;
	while(aux != NULL)
	{
		block_size = b[1][aux->block] - b[0][aux->block] + 1;
		for(i = 0; i < block_size; i++)
			new[newi++] = g[b[0][aux->block] + i];
		aux = aux->next;
	}

	return new;
}

int get_score(char **t, int tsize, int *tsizes, char *g, int gsize)
{
	int i;
	int score = 0;

	for(i = 0; i < tsize; i++)
	{
		if(gsize > tsizes[i])
			score += similarity(g, t[i], gsize, tsizes[i]);
		else
			score += similarity(t[i], g, tsizes[i], gsize);

	}
	return score;
}

void zera_blocos_usados(char *b, int bsize)
{
	int i;
	for(i = 0; i < bsize; i++)
		b[i] = NO;
}

void marca_blocos_usados(struct block *pop, char* blocos_usados, int bsize)
{
	struct block *aux = pop;
	zera_blocos_usados(blocos_usados, bsize);

	/*Marca os blocos já utilizados no indivíduo i*/
	while(aux != NULL)
	{
		blocos_usados[aux->block] = YES;
		aux = aux->next;
	}
}

int try_to_insert(int bsize, char *blocos_usados, struct block **population, struct block **blocos_sobrepostos, int i, int **b, int *tamanho_concat)
{
	int rand_block;
	char sobreposto;
	int itentativas;

	itentativas = 0;

	do
	{
		rand_block = (rand() % (bsize - 1)) + 1;
		sobreposto = YES;
		/*Verifica se o bloco já foi usado e se ele é sobreposto com algum da solução*/
		if(blocos_usados[rand_block] == NO )
		{
			sobreposto = overlap(population[i], blocos_sobrepostos, rand_block);
			if(sobreposto == NO)
			{
				insert_block(&(population[i]), rand_block);
				tamanho_concat[i] += b[1][rand_block] - b[0][rand_block] + 1; /* Calcula o comprimento do bloco */
			}
		}
		itentativas++;
	}while( itentativas < TENTATIVAS_SIZE && (blocos_usados[rand_block] != NO || sobreposto != NO));

	if(itentativas < TENTATIVAS_SIZE)
		return rand_block;
	else
		return -1;
}

void calcula_scores(char *g, char **t, int tsize, int *tsizes, int **b, struct block **population, int popsize, int *tamanho_concat, int *score)
{
	int i;
	char *seq;

	/*Calcula os scores de cada indivíduo*/
	for(i = 0; i < popsize; i++)
	{
		seq = get_sequence(g, b, population[i], tamanho_concat[i]);
		score[i] = get_score(t, tsize, tsizes, seq, tamanho_concat[i]);
		free(seq);
	}
}

int calcula_um_score(char *g, char **t, int tsize, int *tsizes, int **b, struct block **population, int *tamanho_concat, int i)
{
	int score;
	char *seq;

	seq = get_sequence(g, b, population[i], tamanho_concat[i]);
	score = get_score(t, tsize, tsizes, seq, tamanho_concat[i]);
	free(seq);
	return score;
}

void copy_solution(struct block *b, struct block **individuo)
{
	struct block *orig = b;
	struct block *new;
	struct block *pont = NULL;

	while(orig != NULL)
	{
		new = (struct block *) malloc(sizeof(struct block));
		new->block = orig->block;
		new->next = NULL;

		if((*individuo) == NULL)
		{
			(*individuo) = new;
			pont = new;
		}
		else
		{
			pont->next = new;
			pont = new;

		}
		orig = orig->next;
	}
}



struct block *join(struct block *b1, struct block *b2, int index, int **b, int *tam, int *qtd, int tam_qtd_index)
{
	struct block *aux1 = b1;
	struct block *aux2 = b2;
	struct block *new = NULL;
	int i;

	tam[tam_qtd_index] = 0;
	qtd[tam_qtd_index] = 0;

	for(i = 0; i < index; i++)
	{
		insert_block(&new, aux1->block);
		tam[tam_qtd_index] += b[1][aux1->block] - b[0][aux1->block] + 1;
		qtd[tam_qtd_index]++;
		aux1 = aux1->next;
	}
	insert_block(&new, aux1->block);
	tam[tam_qtd_index] += b[1][aux1->block] - b[0][aux1->block] + 1;
	qtd[tam_qtd_index]++;

	while(aux2 != NULL && b[0][aux2->block] <= b[1][aux1->block])
		aux2 = aux2->next;

	while(aux2 != NULL)
	{
		insert_block(&new, aux2->block);
		tam[tam_qtd_index] += b[1][aux2->block] - b[0][aux2->block] + 1;
		qtd[tam_qtd_index]++;
		aux2 = aux2->next;
	}

	tam[tam_qtd_index]++;
	return new;
}

int simulated_insertion_score(char *g, char **t, int tsize, int *tsizes, struct block **population, int i, int **b, int *tamanho_concat, int blococandidato)
{
	char *seq;
	struct block *copia;
	int copiasize;
	int novoscore;

	copia = create_copy_individual(&(population[i]));

	insert_block(&copia, blococandidato);
	copiasize = tamanho_concat[i] + b[1][blococandidato] - b[0][blococandidato] + 1;

	seq = get_sequence(g, b, copia, copiasize);
	novoscore = get_score(t, tsize, tsizes, seq, copiasize);


	free(seq);
	free_blocks(&copia);
	return novoscore;
}

int simulated_deletion_score(char *g, char **t, int tsize, int *tsizes, struct block **population, int i, int **b, int *tamanho_concat, int blocoremovido)
{
	char *seq;
	struct block *copia;
	int copiasize;
	int novoscore;

	copia = create_copy_individual(&(population[i]));

	delete_block_by_content(&copia, blocoremovido);

	copiasize = tamanho_concat[i] - (b[1][blocoremovido] - b[0][blocoremovido] + 1);

	seq = get_sequence(g, b, copia, copiasize);
	novoscore = get_score(t, tsize, tsizes, seq, copiasize);


	free(seq);
	free_blocks(&copia);
	return novoscore;
}
